Resumen de algoritmos para torneos de programación

Andrés Mejía

4 de abril de 2008

Índice

1. Teoría de números 1 1.1. Big mod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2. Criba de Eratóstenes . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3. Divisores de un número . . . . . . . . . . . . . . . . . . . . . . . 2

2. Programación dinámica 2 2.1. Longest common subsequence . . . . . . . . . . . . . . . . . . . . 2

Listings

1. Teoría de números

1.1. Big mod

//retorna (bˆ p)mod(m) // 0 <= b,p <= 2147483647 // 1 <= m <= 46340 long f(long b, long p, long m){ long mask = 1; long pow2 = b % m; long r = 1;

while (mask){

if (p & mask)

r = (r * pow2) % m; pow2 = (pow2*pow2) % m; mask < <= 1; } return r; }

1.2. Criba de Eratóstenes

Marca los números primos en un arreglo. Algunos tiempos de ejecución:

SIZE  Tiempo (s)
100000  0.004
1000000  0.078
10000000  1.550
100000000  14.319

1.3. Divisores de un número

Este algoritmo imprime todos los divisores de un número (en desorden) en

O(\sqrt{n}). Hasta 4294967295 (máximo unsigned long) responde instantaneamente. Se puede forzar un poco más usando unsigned long long

pero más allá de 10^{12} empieza a responder muy lento.

2. Programación dinámica

2.1. Longest common subsequence